import functools


class Solution(object):
    def PredictTheWinner(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        target = sum(nums) / 2
        n = len(nums)

        @functools.cache
        def search(i, j, value1, value2):
            if i == j:
                if value1 + nums[i] > target:
                    return True
                else:
                    if value1 + nums[i] < target:
                        return False
                    else:
                        if n % 2 == 0:
                            return False
                        else:
                            return True
            else:
                flag1 = search(i + 1, j, value2, value1 + nums[i])
                flag2 = search(i, j - 1, value2, value1 + nums[j])
                if flag1 and flag2:
                    return False
                else:
                    return True

        return search(0, len(nums) - 1, 0, 0)


data = Solution()
nums = [1, 1]
print(data.PredictTheWinner(nums))
